package 经典例题;

import java.util.ArrayList;

public class 圆圈中最后剩下的数字 {

    //公式法
    public int lastRemaining1(int n, int m) {
        int p=0;
        for (int i = 2; i <=n ; i++) {
            p=(p+m)%i;
        }
        return p;
    }
    //模拟做法  比较容易理解
    public int lastRemaining2(int n, int m) {
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(i);
        }
        int idx=0;
        while (n>1){
            idx=(idx+m-1)%n;
            list.remove(idx);
            n--;
        }
        return list.get(0);
    }

}
